class Task36:
    def run(self, tree):
        if tree is None:
            return None
        else:
            head, tail = self.run_inner(tree)
            return head

    def run_inner(self, root):
        if root.left is None:
            head = root
        else:
            left_head, left_tail = self.run_inner(root.left)
            left_tail.right = root
            root.left = left_tail
            head = left_head
        if root.right is None:
            tail = root
        else:
            right_head, right_tail = self.run_inner(root.right)
            right_head.left = root
            root.right = right_head
            tail = right_tail
        return head, tail
